/*

T3 - gera de palavras aleatorias e verifica se a palavra esta em uma frase do texto

*/

#include <iostream>
#include <unordered_set>
#include <list>
#include <iterator>
#include <string>

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <ctime>
#include <cmath>

#include "mpi.h"
#include "omp.h"

#define TAM_MAX_PALAVRA 50
#define TAM_BLOCO 26

using namespace std;

typedef struct
{
	char palavra[TAM_MAX_PALAVRA];
}
t_palavra;

int size_block[1] = { TAM_MAX_PALAVRA };

MPI_Aint offset[1] = { 0 };

MPI_Datatype mpi_palavra;

MPI_Datatype type[1] = { MPI_CHAR };


unsigned int gera_num_aleatorio(int n)
{
	return (n * time(NULL) + n);
}

/*
 Gera palavra com no maximo 5 e no minimo 1 letra(s)
*/
void gera_palavra(char *palavra, int tam)
{
	int i;
	char c;
	
	#pragma omp parallel for private(i) shared(palavra,tam)
	for (i = 0; i < tam; i++)
	{
		c = rand() % 26 + 97;
		
		palavra[i] = c;
	}
	#pragma omp barrier
	palavra[tam] = '\0';
}

/*
 Compoe palavra a partir de 2 palavras
*/
void compoe_palavra(string palavra1, string palavra2, string &resp)
{
	resp = palavra1 + palavra2;
}

// remove caracteres nao-alfabeticos de uma string
void pre_processamento(char *palavra)
{
	int i, j = 0;
	int tam = strlen(palavra);
	
	// openMP não funcionou para este for
	//#pragma omp parallel for private(i) shared(palavra)
	for (i = 0; i < tam; i++)
	{
		if (isalpha(palavra[i]))
		{
			palavra[j] = tolower(palavra[i]);
			j++;
		}
	}
	//#pragma omp barrier
	palavra[j] = '\0';
}

int main(int argc, char *argv[])
{
	FILE *f;
	
	unordered_set<string> texto;
	unordered_set<string> palavras_geradas;
	
	list<string> palavras_encontradas;
	list<string> lista_palavras;
	
	unordered_set<string>::iterator it;
	
	list<string>::iterator it2;
	list<string>::iterator it3;
	list<string>::iterator it4;
	
	pair<unordered_set<string>::iterator,bool> inseriu;
	
	MPI_Status status;
	
	int cont_encontradas = 0;
	int total_palavras = 0;
	int total_repetida = 0;
	
	int rc;
	int tag = 1;
	int rank;
	int dest;
	int source;
	int num_proc;
	
	int i;
	int j;
	int tam = 0;
	int soma_flag = 0;
	int achou;
	int marca;
	int marca2;
	int porcentagem = 1;
	
	int flag[20] = {    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0	};
						
	
	int qtde[50] = {    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0	};
	
	int qtde_encontrada[5] = { 0, 0, 0, 0, 0 };
	
	char *pc;
	char buffer[32768];
	char palavra[TAM_MAX_PALAVRA];
	
	string s;
	
	t_palavra vet[TAM_BLOCO];
	
	clock_t inicio;
	clock_t tempo;
	
	f = fopen("palavras.txt", "rb");

	rc = MPI_Init(&argc, &argv);

	if (rc == MPI_SUCCESS)
	{
		// cria o tipo de dado mpi_palavra no MPI
		MPI_Type_struct(1, size_block, offset, type, &mpi_palavra);
		MPI_Type_commit(&mpi_palavra);
		
		MPI_Comm_size(MPI_COMM_WORLD, &num_proc);
		MPI_Comm_rank(MPI_COMM_WORLD, &rank);
		
		srand(gera_num_aleatorio(rank));
		
		if (rank == 0)
		{
			//le todas as frases do arquivo texto e coloca no banco de dados
			while (fscanf(f, "%[^\n]", buffer) != EOF)
			{
				pc = strtok(buffer, ",");
		
				while (pc != NULL)
				{
					pre_processamento(pc);
					
					s = pc;
					
					inseriu = texto.insert(s);
					
					if (inseriu.second)
					{
						qtde[s.length()-1]++;
						total_palavras++;
						
						//cout << s << endl;
					}
					else total_repetida++;
					
					pc = strtok(NULL, ",");
				}
				fseek(f, 1, SEEK_CUR);
			}
			/*
			cout << "qtde[0] " << qtde[0] << endl;
			cout << "qtde[1] " << qtde[1] << endl;
			cout << "qtde[2] " << qtde[2] << endl;
			cout << "qtde[3] " << qtde[3] << endl;
			cout << "qtde[4] " << qtde[4] << endl;
			cout << "qtde palavras " << total_palavras << endl;
			cout << "qtde repetida " << total_repetida << endl;
			*/
			cout << "leitura do arquivo finalizada!" << endl;
			
			inicio = clock();

			//recebe as palavras geradas de ate 5 caracteres e procura no banco
			while (soma_flag < num_proc)
			{
				soma_flag = 1;
					
				for (source = 1; source < num_proc; source++)
				{
					if (flag[source] == 0)
					{
						rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, source, tag, MPI_COMM_WORLD, &status);				
					
						for (i = 0; i < TAM_BLOCO; i++)
						{
							s = vet[i].palavra;
							
							//cout << s <<  endl;
							
							achou = texto.count(s);
						
							if (achou > 0) //achou palavra
							{
								qtde_encontrada[s.length()-1]++;
								
								//cout << "Palavra G = " << s << endl;
								
								palavras_encontradas.push_back(s);
								texto.erase(s);
											
								cont_encontradas++;
							}
						}
						//cin >> lixo;
									
						switch (source)
						{
							case 1:
							{
								if (qtde_encontrada[0] == qtde[0])
								{
									flag[source] = 1;
								}
								break;
							}
							case 2:
							case 3:
							{
								if (qtde_encontrada[1] == qtde[1])
								{
									flag[source] = 1;
								}
								break;
							}
							case 4:
							case 5:
							case 6:
							{
								if (qtde_encontrada[2] == qtde[2])
								{
									flag[source] = 1;
								}
								break;
							} 
							case 7:
							case 8:
							case 9:
							case 10:
							{
								if (qtde_encontrada[3] == qtde[3])
								{
									flag[source] = 1;
								}
								break;
							}
							case 11:
							case 12:
							case 13:
							case 14:
							case 15:
							{
								if (qtde_encontrada[4] == qtde[4])
								{
									flag[source] = 1;
								}
								break;
							}
						}
						rc = MPI_Send(flag, 20, MPI_INT, source, tag, MPI_COMM_WORLD);
					}
				}
				marca = ceil((porcentagem / (float) 100) * total_palavras);
				
				if (cont_encontradas >= marca)
				{
					tempo = clock() - inicio;
					
					//cout << "marca = " << marca << endl;
					//cout << "encontradas = " << cont_encontradas << endl;
			
					printf("\n %3d%% | Quantidade : %6d | tempo : %5.2f s.", porcentagem, cont_encontradas, tempo / (double) CLOCKS_PER_SEC);
					
					porcentagem++;
				}
				#pragma omp parallel for private(i) reduction(+:soma_flag)
				for (i = 1; i < num_proc; i++)
				{
					soma_flag += flag[i];
				}
				#pragma omp barrier
			}
			cout << "geracao de palavras finalizada!" << endl;
			
			// seta as flags para 0
			#pragma omp parallel for private(i) shared(flag,num_proc)
			for (i = 1; i < num_proc; i++)
			{
				flag[i] = 0;
			}
			#pragma omp barrier
			it3 = palavras_encontradas.begin();
			
			//envia todas as palavras encontradas nos nos escravos
			while (distance(it3, palavras_encontradas.end()) >= TAM_BLOCO)
			{
				for (i = 0; i < TAM_BLOCO; i++)
				{
					s = *it3;
					strcpy(vet[i].palavra, s.c_str());
					it3++;
				}
				for (dest = 1; dest < num_proc; dest++)
				{
					rc = MPI_Send(flag, 20, MPI_INT, dest, tag, MPI_COMM_WORLD);
					rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
				}	
			}
			// seta as flags para 1
			#pragma omp parallel for private(i) shared(num_proc,flag)
			for (i = 1; i < num_proc; i++)
			{
				flag[i] = 1;
			}
			#pragma omp barrier
			for (dest = 1; dest < num_proc; dest++)
			{
				rc = MPI_Send(flag, 20, MPI_INT, dest, tag, MPI_COMM_WORLD);	
			}
			cout << "envio das palavras para os nós auxiliares finalizado!" << endl;

			soma_flag = 0;
			
			// seta as flags para 1
			#pragma omp parallel for private(i) shared(num_proc,flag)
			for (i = 1; i < num_proc; i++)
			{
				flag[i] = 0;
			}
			#pragma omp barrier
			
			//encontra as palavras com mais de 5 caracteres geradas pelos escravos
			while (soma_flag < num_proc)
			{
				soma_flag = 1;
				
				for (source = 1; source < num_proc; source++)
				{
					if (flag[source] == 0)
					{
						rc = MPI_Recv(&flag[source], 1, MPI_INT, source, tag, MPI_COMM_WORLD, &status);				
						//cout << "recebeu flag..." << source << endl;
						
						if (flag[source] == 0)
						{
							rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, source, tag, MPI_COMM_WORLD, &status);
							//cout << "recebeu...!" << source << endl;
					
						
							for (i = 0; i < TAM_BLOCO; i++)
							{
								s = vet[i].palavra;
								achou = texto.count(s);
						
								if (achou > 0) //achou palavra
								{
									//cout << "Palavra C = " << s << endl;
								
									palavras_encontradas.push_back(s);
									texto.erase(s);
											
									cont_encontradas++;
								}
							}
						}
					}
				}
				//cout << "recebeu e buscou todos!" << endl;
				
				marca = ceil((porcentagem / (float) 100) * total_palavras);
				
				if (cont_encontradas >= marca)
				{
					tempo = clock() - inicio;
					
					//cout << "marca = " << marca << endl;
					//cout << "encontradas = " << cont_encontradas << endl;
			
					printf("\n %3d%% | Quantidade : %6d | tempo : %5.2f s.", porcentagem, cont_encontradas, tempo / (double) CLOCKS_PER_SEC);
			
					porcentagem ++;
				}
				if (distance(it3, palavras_encontradas.end()) >= TAM_BLOCO)
				{
					//cout << "inicio if" << endl;
					for (i = 0; i < TAM_BLOCO; i++)
					{
						s = *it3;
						strcpy(vet[i].palavra, s.c_str());
						it3++;
					}
					//cout << "fim if" << endl;			
				}
				else
				{
					//cout << "inicio else" << endl;
				
					for (i = 0; i < distance(it3, palavras_encontradas.end()); i++)
					{
						s = *it3;
						strcpy(vet[i].palavra, s.c_str());
						it3++;
					}
					//it4 = palavras_encontradas.begin();
					//cout << "meio do else" << endl;
					
					s = "_lixo_";
					
					for ( ; i < TAM_BLOCO; i++)
					{
						strcpy(vet[i].palavra, s.c_str());
					}
					//cout << "fim else" << endl;	
				}
				//cout << "montou bloco!" << endl;
				
				for (dest = 1; dest < num_proc; dest++)
				{
					if (flag[dest] == 0)
					{
						rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
					}
				}
				//cout << "enviou bloco!" << endl;
				#pragma omp parallel for private(i) reduction(+:soma_flag)
				for (i = 1; i < num_proc; i++)
				{
					soma_flag += flag[i];
				}
			}
			cout << "encontradas : " << cont_encontradas << endl;
			
			//for (it2 = palavras_encontradas.begin(); it2 != palavras_encontradas.end(); it2++)
			//{
			//    cout << *it2 << endl;
			//}
			
			texto.clear();
			palavras_encontradas.clear();
			
			cout << "saiu rank 0" << endl;
		}
		if (rank == 1)
		{
			dest = 0;
			source = rank;
				
			//gera as palavras de 1 caracter e manda para o rank 0
			while (flag[rank] == 0)
			{
				while (tam < TAM_BLOCO)
				{	
					gera_palavra(palavra, 1);
					
					s = palavra;
					//cout << s << endl;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						palavras_geradas.insert(s);
						strcpy(vet[tam].palavra, palavra);
						
						tam++;
					}
				}
				tam = 0;
				
				//cout << "enviando..." << endl;
				rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
				
				//cout << "recebendo..." << endl;
				rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);	
			}
	
			// popula o conjunto local com palavras aletorias de tamanho 1 a 4
			for (it = palavras_geradas.begin(); it != palavras_geradas.end(); it++)
			{
				lista_palavras.push_back(*it);
			}
			cout << "rank 1 - conjunto de palavras copiado para a lista!" << endl;  
			
			for (i = 2; i < 5; i++)
			{	
				j = 0;
				marca2 = floor(0.25 * pow(26, i)); 
			
				do
				{
					//cout << "gerando..." << rank << i << endl;
				
					gera_palavra(palavra, i);
				
				   	s = palavra;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						lista_palavras.push_back(s);
						j++;
					}	
				}
				while (j < marca2);
			}
			cout << "rank 1 - lista preenchida com palavras aleatórias!" << endl;
			
			rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			
			//recebe o vetor de palavras encontradas no no 0
			while (flag[rank] == 0)
			{
				rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, 0, tag, MPI_COMM_WORLD, &status);
				
				for (i = 0; i < TAM_BLOCO; i++)
				{
					s = vet[i].palavra;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						lista_palavras.push_back(s);
					}
				}
				rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			}
			cout << "rank 1 - recebimento da lista de palavras do no 0 finalizado!" << endl;
			
			//for (it2 = lista_palavras.begin(); it2 != lista_palavras.end(); it2++)
			//{
			//    cout << *it2 << endl;
			//} 
			
			flag[rank] = 0;
			
			it3 = lista_palavras.begin();
			it4 = lista_palavras.begin(); 
			
			advance(it3, rank-1);
			
			//compoe palavras e manda para o no mestre
			while (flag[rank] == 0)
			{
				while (distance(it3, lista_palavras.end()) >= num_proc)
				{
					while (distance(it4, lista_palavras.end()) >= (TAM_BLOCO / 2))
					{
						rc = MPI_Send(&flag[rank], 1, MPI_INT, dest, tag, MPI_COMM_WORLD);
						//cout << "enviou flag..." << rank << endl;	
						//#pragma omp parallel for private(i)
						for (i = 0; i < (TAM_BLOCO / 2); i++)
						{
							compoe_palavra(*it3, *it4, s);
							strcpy(vet[2*i].palavra, s.c_str());
							//cout << s << endl;
							compoe_palavra(*it4, *it3, s);
							strcpy(vet[2*i+1].palavra, s.c_str());
							//cout << s << endl;
							
							it4++;
						}
						//#pragma omp barrier
						rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
						//cout << "enviou bloco..." << rank << endl;
						
						rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, 0, tag, MPI_COMM_WORLD, &status);
						//cout << "recebeu bloco..." << rank << endl;
						
						for (i = 0; i < TAM_BLOCO; i++)
						{
							s = vet[i].palavra;
							
							if (s.compare("_lixo_") != 0)
							{
								lista_palavras.push_back(s);
							}
						}
					}
					advance(it3, num_proc-1);	
				}
				flag[rank] = 1;	
			}
			rc = MPI_Send(&flag[rank], 1, MPI_INT, dest, tag, MPI_COMM_WORLD);
			
			palavras_geradas.clear();
			lista_palavras.clear();
			
			cout << "saiu rank 1" << endl;
		}
		
		if (rank >= 2 && rank < 4)
		{
			dest = 0;
			source = rank;
			
			//gera as palavras de 2 caracteres e manda para o rank 0
			while (flag[rank] == 0)
			{
				while (tam < TAM_BLOCO)
				{	
					gera_palavra(palavra, 2);
					
					s = palavra;
					//cout << s << endl;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						palavras_geradas.insert(s);
						strcpy(vet[tam].palavra, palavra);
						
						tam++;
					}
				}
				tam = 0;
				
				//cout << "enviando..." << endl;
				rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
				//cout << "recebendo..." << endl;
				rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			}
			//cout << "copiando ..." << endl;
			
			for (it = palavras_geradas.begin(); it != palavras_geradas.end(); it++)
			{
				lista_palavras.push_back(*it);
			}
			cout << "rank 2..3 - conjunto de palavras copiado para a lista!" << endl;  
			
			for (i = 1; i < 5; i++)
			{
				if (i != 2)
				{
				    j = 0;
				    marca2 = floor(0.25 * pow(26, i)); 
			
				    do
				    {
					    gera_palavra(palavra, i);
				
				       	s = palavra;
					
					    achou = palavras_geradas.count(s);
					
					    if (achou == 0)
					    {
						    lista_palavras.push_back(s);
						    j++;
					    }	
				    }
				    while (j < marca2);
				}
			}
			cout << "rank 2..3 - lista preenchida com palavras aleatórias!" << endl;
		
			rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			
			//recebe as palavras encontradas no rank 0
			while (flag[rank] == 0)
			{
				rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, 0, tag, MPI_COMM_WORLD, &status);
				
				for (i = 0; i < TAM_BLOCO; i++)
				{
					s = vet[i].palavra;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						lista_palavras.push_back(s);
					}
				}
				rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			}
			cout << "rank 2..3  - recebimento da lista de palavras do no 0 finalizado!" << endl;
			
			flag[rank] = 0;
			
			it3 = lista_palavras.begin();
			it4 = lista_palavras.begin(); 
			
			advance(it3, rank-1);
			
			//compoe palavras e manda para o rank 0
			while (flag[rank] == 0)
			{
				while (distance(it3, lista_palavras.end()) >= num_proc)
				{
					while (distance(it4, lista_palavras.end()) >= (TAM_BLOCO / 2))
					{
						rc = MPI_Send(&flag[rank], 1, MPI_INT, dest, tag, MPI_COMM_WORLD);	
						
						//cout << "enviou flag..." << rank << endl;
						//#pragma omp parallel for private(i)
						for (i = 0; i < (TAM_BLOCO / 2); i++)
						{
							compoe_palavra(*it3, *it4, s);
							strcpy(vet[2*i].palavra, s.c_str());
							//cout << s << endl;
							compoe_palavra(*it4, *it3, s);
							strcpy(vet[2*i+1].palavra, s.c_str());
							//cout << s << endl;
							
							it4++;
						}
						//#pragma omp barrier
						rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
						//cout << "enviou bloco..." << rank << endl;
						rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, 0, tag, MPI_COMM_WORLD, &status);
						//cout << "recebeu bloco..." << rank << endl;
						
						for (i = 0; i < TAM_BLOCO; i++)
						{
							s = vet[i].palavra;
							
							if (s.compare("_lixo_") != 0)
							{
								lista_palavras.push_back(s);
							}
						}
					}
					advance(it3, num_proc-1);	
				}
				flag[rank] = 1;	
			}
			rc = MPI_Send(&flag[rank], 1, MPI_INT, dest, tag, MPI_COMM_WORLD);
			
			palavras_geradas.clear();
			lista_palavras.clear();
			
			cout << "saiu rank " << rank << endl;
		}
        
		if (rank >= 4 && rank < 7)
		{
			dest = 0;
			source = rank;
			
			//gera as palavras de 3 caracteres e manda para o rank 0
			while (flag[rank] == 0)
			{
				while (tam < TAM_BLOCO)
				{	
					gera_palavra(palavra, 3);
					
					s = palavra;
					//cout << s << endl;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						palavras_geradas.insert(s);
						strcpy(vet[tam].palavra, palavra);
						
						tam++;
					}
				}
				tam = 0;
				
				rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
				rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			}
			for (it = palavras_geradas.begin(); it != palavras_geradas.end(); it ++)
			{
				lista_palavras.push_back(*it);
			}
			cout << "rank 4..6 - conjunto de palavras copiado para a lista!" << endl;  
			
			for (i = 1; i < 5; i++)
			{
				if (i != 3)
				{
				    j = 0;
				    marca2 = floor(0.25 * pow(26, i)); 
			
				    do
				    {
					    gera_palavra(palavra, i);
				
				       	s = palavra;
					
					    achou = palavras_geradas.count(s);
					
					    if (achou == 0)
					    {
						    lista_palavras.push_back(s);
						    j++;
					    }	
				    }
				    while (j < marca2);
				}
			}
			cout << "rank 4..6 - lista preenchida com palavras aleatórias!" << endl;
	
			rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			
			//recebe as palavras do rank 0
			while (flag[rank] == 0)
			{
				rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, 0, tag, MPI_COMM_WORLD, &status);
				
				for (i = 0; i < TAM_BLOCO; i++)
				{
					s = vet[i].palavra;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						lista_palavras.push_back(s);
					}
				}
				rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			}
			cout << "rank 4..6 - recebimento da lista de palavras do no 0 finalizado!" << endl;
			
			flag[rank] = 0;
			
			it3 = lista_palavras.begin();
			it4 = lista_palavras.begin(); 
			
			advance(it3, rank-1);
			
			//compoe palavras e manda para o rank 0
			while (flag[rank] == 0)
			{
				while (distance(it3, lista_palavras.end()) >= num_proc)
				{
					while (distance(it4, lista_palavras.end()) >= (TAM_BLOCO / 2))
					{
						rc = MPI_Send(&flag[rank], 1, MPI_INT, dest, tag, MPI_COMM_WORLD);	
						//#pragma omp parallel for private(i)
						for (i = 0; i < (TAM_BLOCO / 2); i++)
						{
							compoe_palavra(*it3, *it4, s);
							strcpy(vet[2*i].palavra, s.c_str());
							//cout << s << endl;
							compoe_palavra(*it4, *it3, s);
							strcpy(vet[2*i+1].palavra, s.c_str());
							//cout << s << endl;
							
							it4++;
						}
						//#pragma omp barrier
						rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
						rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, 0, tag, MPI_COMM_WORLD, &status);
						
						for (i = 0; i < TAM_BLOCO; i++)
						{
							s = vet[i].palavra;
							
							if (s.compare("_lixo_") != 0)
							{
								lista_palavras.push_back(s);
							}
						}
					}
					advance(it3, num_proc-1);	
				}
				flag[rank] = 1;	
			}
			rc = MPI_Send(&flag[rank], 1, MPI_INT, dest, tag, MPI_COMM_WORLD);
			
			palavras_geradas.clear();
			lista_palavras.clear();
			
			cout << "saiu rank " << rank << endl;
		}
		
		if (rank >= 7 && rank < 11)
		{
			dest = 0;
			source = rank;
			
			//gera as palavras de 4 caracteres e manda para o rank 0
			while (flag[rank] == 0)
			{
				while (tam < TAM_BLOCO)
				{	
					gera_palavra(palavra, 4);
					
					s = palavra;
					//cout << s << endl;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						palavras_geradas.insert(s);
						strcpy(vet[tam].palavra, palavra);
						
						tam++;
					}
				}
				tam = 0;
				
				rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
				rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);	
			}
			for (it = palavras_geradas.begin(); it != palavras_geradas.end(); it++)
			{
				lista_palavras.push_back(*it);
			}
			cout << "rank 7..10 - conjunto de palavras copiado para a lista!" << endl;  
			
			for (i = 1; i < 5; i++)
			{
				if (i != 4)
				{
				    j = 0;
				    marca2 = floor(0.25 * pow(26, i)); 
			
				    do
				    {
					    gera_palavra(palavra, i);
				
				       	s = palavra;
					
					    achou = palavras_geradas.count(s);
					
					    if (achou == 0)
					    {
						    lista_palavras.push_back(s);
						    j++;
					    }	
				    }
				    while (j < marca2);
				}
			}
			cout << "rank 7..10 - lista preenchida com palavras aleatórias!" << endl;
			
			rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			
			//recebe as palavras do rank 0
			while (flag[rank] == 0)
			{
				rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, 0, tag, MPI_COMM_WORLD, &status);
				
				for (i = 0; i < TAM_BLOCO; i++)
				{
					s = vet[i].palavra;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						lista_palavras.push_back(s);
					}
				}
				rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			}
			cout << "rank 7..10 - recebimento da lista de palavras do no 0 finalizado!" << endl;
			
			flag[rank] = 0;
			
			it3 = lista_palavras.begin();
			it4 = lista_palavras.begin(); 
			
			advance(it3, rank-1);
			
			//compoe palavras e manda para o rank 0
			while (flag[rank] == 0)
			{
				while (distance(it3, lista_palavras.end()) >= num_proc)
				{
					while (distance(it4, lista_palavras.end()) >= (TAM_BLOCO / 2))
					{
						rc = MPI_Send(&flag[rank], 1, MPI_INT, dest, tag, MPI_COMM_WORLD);	
						//#pragma omp parallel for private(i)
						for (i = 0; i < (TAM_BLOCO / 2); i++)
						{
							compoe_palavra(*it3, *it4, s);
							strcpy(vet[2*i].palavra, s.c_str());
							//cout << s << endl;
							compoe_palavra(*it4, *it3, s);
							strcpy(vet[2*i+1].palavra, s.c_str());
							//cout << s << endl;
							
							it4++;
						}
						//#pragma omp barrier
						rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
						rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, 0, tag, MPI_COMM_WORLD, &status);
						
						for (i = 0; i < TAM_BLOCO; i++)
						{
							s = vet[i].palavra;
							
							if (s.compare("_lixo_") != 0)
							{
								lista_palavras.push_back(s);
							}
						}
					}
					advance(it3, num_proc-1);	
				}
				flag[rank] = 1;	
			}
			rc = MPI_Send(&flag[rank], 1, MPI_INT, dest, tag, MPI_COMM_WORLD);
			
		    cout << "saiu rank " << rank << endl;
		}
		
		if (rank >= 11 && rank < num_proc)
		{
			dest = 0;
			source = rank;
			
			//gera as palavras de 5 caracteres e manda para o rank 0
			while (flag[rank] == 0)
			{
				while (tam < TAM_BLOCO)
				{	
					gera_palavra(palavra, 5);
					
					s = palavra;
					//cout << s << endl;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						palavras_geradas.insert(s);
						strcpy(vet[tam].palavra, palavra);
						
						tam++;
					}
				}
				tam = 0;
				
				rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
				rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);	
			}
			for (it = palavras_geradas.begin(); it != palavras_geradas.end(); it ++)
			{
				lista_palavras.push_back(*it);
			}
			cout << "rank 11..15 - conjunto de palavras copiado para a lista!" << endl;  
			
			for (i = 1; i < 5; i++)
			{	
			    j = 0;
			    marca2 = floor(0.25 * pow(26, i)); 
		
			    do
			    {
				    gera_palavra(palavra, i);
			
			       	s = palavra;
				
				    achou = palavras_geradas.count(s);
				
				    if (achou == 0)
				    {
					    lista_palavras.push_back(s);
					    j++;
				    }	
			    }
			    while (j < marca2);
			}
			cout << "rank 11..15 - lista preenchida com palavras aleatórias!" << endl;
			
			rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			
			//recebe as palavras do rank 0
			while (flag[rank] == 0)
			{
				rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, 0, tag, MPI_COMM_WORLD, &status);
				
				for (i = 0; i < TAM_BLOCO; i++)
				{
					s = vet[i].palavra;
					
					achou = palavras_geradas.count(s);
					
					if (achou == 0)
					{
						lista_palavras.push_back(s);
					}
				}
				rc = MPI_Recv(flag, 20, MPI_INT, 0, tag, MPI_COMM_WORLD, &status);
			}
			cout << "rank 11..15 - recebimento da lista de palavras do no 0 finalizado!" << endl;
			
			flag[rank] = 0;
			
			it3 = lista_palavras.begin();
			it4 = lista_palavras.begin(); 
			
			advance(it3, rank-1);
			
			//compoe palavras e manda para o rank 0
			while (flag[rank] == 0)
			{
				while (distance(it3, lista_palavras.end()) >= num_proc)
				{
					while (distance(it4, lista_palavras.end()) >= (TAM_BLOCO / 2))
					{
						rc = MPI_Send(&flag[rank], 1, MPI_INT, dest, tag, MPI_COMM_WORLD);	
						//#pragma omp parallel for private(i)
						for (i = 0; i < (TAM_BLOCO / 2); i++)
						{
							compoe_palavra(*it3, *it4, s);
							strcpy(vet[2*i].palavra, s.c_str());
							//cout << s << endl;
							compoe_palavra(*it4, *it3, s);
							strcpy(vet[2*i+1].palavra, s.c_str());
							//cout << s << endl;
							
							it4++;
						}
						//#pragma omp barrier
						rc = MPI_Send(vet, TAM_BLOCO, mpi_palavra, dest, tag, MPI_COMM_WORLD);
						rc = MPI_Recv(vet, TAM_BLOCO, mpi_palavra, 0, tag, MPI_COMM_WORLD, &status);
						
						for (i = 0; i < TAM_BLOCO; i++)
						{
							s = vet[i].palavra;
							
							if (s.compare("_lixo_") != 0)
							{
								lista_palavras.push_back(s);
							}
						}
					}
					advance(it3, num_proc-1);	
				}
				flag[rank] = 1;	
			}
			rc = MPI_Send(&flag[rank], 1, MPI_INT, dest, tag, MPI_COMM_WORLD);
			
			cout << "saiu rank " << rank << endl;
		}
				
	}
	fclose(f);
	
	MPI_Finalize();
	
	return 0;
}
